package red.book._1._5;

public class WeightedQuickUnionUFTest {
	private int[] id; // parent link (site indexed)
	private int[] sz; // size of component for roots (site indexed)
	private int count; // number of components

	public WeightedQuickUnionUFTest(int N) {
		count = N;
		id = new int[N];
		sz = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}

	public int count() {
		return count;
	}

	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}

	private int find(int p) { // Follow links to find a root.
		while(p != id[p]) {
			p = id[p];
		}
		return p;
	}

	public void union(int p, int q) {
		int pl = find(p);
		int ql = find(q);
		
		if(pl == ql)
			return;
		
		if(sz[pl] < sz[ql]) {
			id[pl] = ql;
			sz[ql] += sz[pl];
		}else {
			id[ql] = pl;
			sz[pl] += sz[ql];
		}
		count--;
	}
	
	public static void main(String[] args) {
		WeightedQuickUnionUFTest uf = new WeightedQuickUnionUFTest(10);
		uf.union(4, 3);
		uf.union(3, 8);
		System.out.println(uf.count);
	}
}
